#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cstring>
using namespace std;


class Solution {
private:
    int m,n;
    int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    bool *used;
    bool ans = false;
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        used = new bool[m*n];
        memset(used,false,m*n);
        for(int i =0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j] == word[0]){
                    Helper(board,word,i,j,1);
                }
            }
        }
        delete[] used;
        used = nullptr;
        return ans;
    }

    void Helper(vector<vector<char>>& board,string word,int i,int j,int ix){
        if(i>=m || i<0 || j>=n || j<0){
            return;
        }
        if(ix >= word.size()){
            ans = true;
            return;
        }
        for(int k=0;k<4;k++){
            int newI = i+dir[k][0];
            int newJ = j+dir[k][1];
            if(newI<m && newI>=0 && newJ < n && newJ>=0 && !used[newI*n+newJ] && board[newI][newJ] == word[ix]){
                used[i*n+j] = true;
                Helper(board,word,newI,newJ,ix+1);
                used[i*n+j] = false;
            }
        }
    }
};


int main(){
    Solution solution;
    vector<vector<char>> input = {{'c','a','a'},{'a','a','a'},{'b','c','d'}};
    string word = "aab";
    bool res = solution.exist(input,word);
    cout<<res<<endl;
    // solution.maxSubArray(input);
    return 0;
}
